package com;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * @author CY
 * @date 2022/10/19 20:40
 **/
public class Sort {
    //插入排序
    public static void insetSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                if (arr[j] > tmp) {
                    arr[j + 1] = arr[j];
                } else {
                    arr[j + 1] = tmp;
                    break;
                }
            }
            //排除当j小标为-1的情况
            arr[j + 1] = tmp;
        }
    }

    //选择排序
    public static void selectSort(int[] array) {
        // write code  here
        for (int i = 0; i < array.length; i++) {
            int j = i + 1;
            int minIndex = i;
            for (; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }

            int tmp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = tmp;
        }
    }

    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap /= 2;
            insetSortShell(array, gap);
        }
    }

    private static void insetSortShell(int[] array, int gap) {
        for (int i = gap; i < array.length; i++) {
            int j = i - gap;
            int tmp = array[i];
            for (; j >= 0; j -= gap) {
                //插入排序是和记录的tmp作比较
                if (array[j] > tmp) {
                    array[j + gap] = array[j];
                } else {
                    array[j + gap] = tmp;
                    break;
                }
            }
            array[j + gap] = tmp;
        }
    }

    //堆排序
    public static void heapSort(int[] array) {
        creatHeap(array);
        for (int i = 0; i < array.length; i++) {
            swap(array, 0, array.length - 1 - i);
            for (int parent = (array.length - 2 - i) / 2; parent >= 0; parent--) {
                shiftDown(array, parent, array.length - 1 - i);
            }
        }
    }

    private static void creatHeap(int[] array) {
        for (int parent = (array.length - 2) / 2; parent >= 0; parent--) {
            shiftDown(array, parent, array.length);
        }
    }

    private static void shiftDown(int[] arr, int parent, int len) {
        int child = 2 * parent + 1;
        while (child < len) {
            if (child + 1 < len && arr[child] < arr[child + 1]) {
                child++;
            }
            if (arr[child] > arr[parent]) {
                swap(arr, child, parent);
            }
            parent = child;
            child = 2 * parent + 1;
        }
    }

    private static void swap(int[] arr, int child, int parent) {
        int tmp = arr[child];
        arr[child] = arr[parent];
        arr[parent] = tmp;
    }

    //冒泡
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = true;
            for (int i1 = 0; i1 < array.length - 1 - i; i1++) {
                if (array[i1] > array[i1 + 1]) {
                    swap(array, i1, i1 + 1);
                    flag = false;
                }
            }
            if (flag == true) {
                break;
            }
        }
    }

    //快速排序（递归版本）
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }

    private static void quick(int[] array, int s, int e) {
        while (s >= e) {//此处的大于号是为了排除类似1，2，3，4这样的情况，避免了数组越界
            return;
        }
        //快速排序的两点优化
        //找到指定区间内中间下表，然后找到（开始位置，结束位置，中间位置）的中间值放到起始位置作为key值，这样能避免只有左树，或者只有右树的情况
        //优化1（三数取中法）
        int midIndex = findMiddleIndex(array, s, e);
        swap(array, midIndex, s);

        //当数据量在较小时，可以用插入排序进行排序
        if (e - s + 1 <= 15) {
            for (int i = s + 1; i <= e; i++) {
                int tmp = array[i];
                int j = i - 1;
                for (; j >= s; j--) {
                    if (array[j] > tmp) {
                        array[j + 1] = array[j];
                    } else {
                        array[j + 1] = tmp;
                    }
                }
                array[j + 1] = tmp;
            }
            return;
        }

        int pivot = find(array, s, e);
        quick(array, s, pivot - 1);
        quick(array, pivot + 1, e);

    }

    private static int findMiddleIndex(int[] array, int s, int e) {
        int middleIndex = s + (e - s) / 2;
        if (array[s] < array[e]) {
            if (array[middleIndex] < array[s]) {
                return s;
            } else if (array[middleIndex] > array[e]) {
                return e;
            } else {
                return middleIndex;
            }
        } else {
            if (array[middleIndex] < array[e]) {
                return e;
            } else if (array[middleIndex] > array[s]) {
                return s;
            } else {
                return middleIndex;
            }

        }
    }

    private static int find(int[] array, int s, int e) {
        //Hoare
//        int left = s;
//        while (s < e) {
//            while (s < e && array[e] > array[left]) {
//                e--;
//            }
//            while (s < e && array[s] < array[left]) {
//                s++;
//            }
//            swap(array, s, e);
//        }
//        return e;
        //前后指针
//        int prev = s;
//        int cur = s + 1;
//        while (cur <= e) {
//            if (array[cur] < array[s] && array[++prev] != array[cur]) {
//                swap(array, cur, prev);
//            }
//            cur++;
//        }
//        swap(array, s, prev);
//        return prev;
        //挖坑法
        int pivot = array[s];
        while (s < e) {
            while (s < e && array[e] >= pivot) {
                e--;
            }
            array[s] = array[e];
            while (s < e && array[s] <= pivot) {
                s++;
            }
            array[e] = array[s];
        }
        array[s] = pivot;
        return s;
    }

    //快速排序（非递归）
    public static void quickSortNonRecursive(int[] array) {
        Stack<Integer> sk = new Stack<Integer>();
        int left = 0;
        int right = array.length - 1;
        sk.push(left);
        sk.push(right);

        int pivot = find(array, left, right);

        if (pivot > left + 1) {
            sk.push(left);
            sk.push(pivot - 1);
        }
        if (pivot < right - 1) {
            sk.push(pivot + 1);
            sk.push(right);
        }
        while (!sk.isEmpty()) {
            //这里一定是要先拿出右边的元素（因为栈是一种后进先出的结构）
            right = sk.pop();
            left = sk.pop();
            pivot = find(array, left, right);

            if (pivot > left + 1) {
                sk.push(left);
                sk.push(pivot - 1);
            }
            if (pivot < right - 1) {
                sk.push(pivot + 1);
                sk.push(right);
            }
        }
    }

    private static void initArrNotOrder(int[] arr) {
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10000);
        }
    }

    private static void initArrOrder(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i + 1;
        }
    }

    //归并排序
    public static void mergeSort(int[] array) {
        mergeSortChild(array, 0, array.length - 1);
    }

    //归并排序递归版本
    private static void mergeSortChild(int[] array, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSortChild(array, left, mid);
        mergeSortChild(array, mid + 1, right);
        merge(array, mid, left, right);
    }

    private static void mergeSortNonRecursive(int[] array) {
        int gap = 1;
        while (gap <= array.length - 1) {
            for (int i = 0; i <= array.length; i += gap) {
                int left = i;
                int mid = left + gap - 1;
                //mid和right可能会发生数组越界的情况，需要更新为数组长度
                if(mid>=array.length-1){
                    mid=array.length-1;
                }
                int right = left + gap;
                if(right>=array.length-1){
                    right=array.length-1;
                }
                merge(array, mid, left, right);
            }
            gap *= 2;
        }
    }

    private static void merge(int[] array, int mid, int left, int right) {
        int[] tmp = new int[left + right + 1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        while (s1 <= e1 && s2 <= e2) {
            tmp[k++] = array[s1] < array[s2] ? array[s1++] : array[s2++];
        }
        while (s1 <= e1) {
            tmp[k++] = array[s1++];
        }
        while (s2 < e2) {
            tmp[k++] = array[s2++];
        }
        for (int i = 0; i < k; i++) {
            array[i + left] = tmp[i];
}
    }

    public static void main(String[] args) {
        BigInteger bigInteger = new BigInteger("555555555555555555555555555555555555555555");


    }


    public static void main1(String[] args) {
        int[] arr = new int[10000];
//        initArrOrder(arr);
        initArrNotOrder(arr);
        long start = System.currentTimeMillis();
//        insetSort(arr);
//        selectSort(arr);
//        shellSort(arr);
//        heapSort(arr);
//        bubbleSort(arr);
//        quickSortNonRecursive(arr);
//        mergeSort(arr);
        mergeSortNonRecursive(arr);
        System.out.println(Arrays.toString(arr));
        long end = System.currentTimeMillis();
        System.out.println("排序耗时：" + (end - start) + " ms");
    }


}
